package com.caoyanan.algorithm.question.zuoTraining.training003.class08;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.Arrays;

/**
 * 现有n1+n2种面值的硬币，其中前n1种为普通币，可以取任意枚，
 * 后n2种为纪念币， 每种最多只能取一枚，每种硬币有一个面值，
 * 问能用多少种方法拼出m的面值?
 *
 * @author: caoyanan
 * @time: 2021/5/26 3:06 下午
 */
public class Question04_CoinPutTogether {

    public static void main(String[] args) {
        int i1 = putTogetherCoins(new int[]{1, 2, 3}, new int[]{1}, 5);
        System.out.println(i1);

        //dp[1][5]应该是2 //检查出dp[0][0]应该是1
        int[][] dp1 = commemorativeCoinDp(new int[]{5, 5, 8, 2, 5}, 20);
        int[][] dp = ordinaryCoinDp(new int[]{2, 7, 4}, 30);
        int count = 1000;
        int m = 20;
        for (int i = 0; i < count; i++) {
            int[] ordinaryCoins = LogarithmInputGenerator.getInstance().generateRandomArray(5, 8);
            int[] commemorativeCoins = LogarithmInputGenerator.getInstance().generateRandomArray(5, 8);
            System.out.printf("普通币:%s, 纪念币:%s,拼凑 %s ",
                    Arrays.toString(ordinaryCoins), Arrays.toString(commemorativeCoins), m);
            int methods = putTogetherCoins(ordinaryCoins, commemorativeCoins, m);
            System.out.printf("一共有 %s 方式", methods);
            System.out.println();
        }
    }

    private static int putTogetherCoins(int[] ordinaryCoins, int[] commemorativeCoins, int aim) {

        int[][] commemorativeCoinDp = commemorativeCoinDp(commemorativeCoins, aim);

        int[][] ordinaryCoinDp = ordinaryCoinDp(ordinaryCoins, aim);

        if (commemorativeCoinDp == null && ordinaryCoinDp == null) {
            return 0;
        }
        if (commemorativeCoinDp == null) {
            return ordinaryCoinDp[ordinaryCoins.length-1][aim];
        }
        if (ordinaryCoinDp == null) {
            return commemorativeCoinDp[commemorativeCoins.length-1][aim];
        }
        System.out.printf("单独使用纪念币的方法数是: %s ", commemorativeCoinDp[commemorativeCoins.length-1][aim]);
        System.out.printf("单独使用普通币的方法数是: %s ", ordinaryCoinDp[ordinaryCoins.length-1][aim]);

        int sum = 0;
        for (int i = 0; i <= aim; i++) {
            sum += commemorativeCoinDp[commemorativeCoins.length-1][i] * ordinaryCoinDp[ordinaryCoins.length-1][aim-i];
        }
        return sum;
    }

    /**
     * 普通币dp[i][j],表示使用0到i位置的币，拼凑出j有多少种可能方法
     * 首先第一列，使用i个币，拼凑出0，只有1中方法，什么都不用，即dp[i][0] = 1;
     * 然后第一行，只使用1个币，拼抽出j元，有多少种方法，dp[0][k*arr[0]] = 1, k <= dp[0].length / arr[0]
     * 对于一个普遍位置dp[i][j]，首先，不用i币，即dp[i-1][j]
     * 然后，使用一次i币， dp[i-1][j-arr[i]]，也可以使用2次i币，即 dp[i-1][j-2*arr[i]] ...dp[i-1][j-k*arr[i]], k >= j / arr[i]
     * 所以 dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i]] + dp[i-1][j-2*arr[i]] + ... + dp[i-1][j-k*arr[i]],k >= j / arr[i]
     * 通过观察，可以有一个斜率优化，发现 dp[i][j-arr[i]]正好就等于 dp[i-1][j-arr[i]] + dp[i-1][j-2*arr[i] + ... + dp[i-1][j-k*arr[i]]
     * 所以 dp[i][j] = dp[i-1][j] + dp[i][j-arr[i]]
     * @param coins
     * @param aim
     * @return
     */
    private static int[][] ordinaryCoinDp(int[] coins, int aim) {

        if (coins == null || coins.length == 0) {
            return null;
        }

        int[][] dp = new int[coins.length][aim+1];

        for (int i = 0; i < coins.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i <= aim / coins[0]; i++) {
            dp[0][i*coins[0]] = 1;
        }
        for (int i = 1; i < coins.length; i++) {
            for (int j = 1; j <= aim; j++) {
                int choose = 0;
                if (j - coins[i] >= 0) {
                    choose =  dp[i][j - coins[i]];
                }
                dp[i][j] = dp[i - 1][j] + choose;
            }
        }
        return dp;
    }

    /**
     * 纪念币dp[i][j],表示选0到i位置的纪念币情况下，拼凑出j元的方法数
     * 首先第一行，dp[0][0] = 1, dp[0][arr[0]=1,其他都是0；
     * 第一列，用i个币拼凑0元，只有1种方法，就是不用任何币，所以dp[i][0] = 1
     * 对于一个普遍位置dp[i][j]。首先，不用i位置的币，dp[i-1][j]，或者使用i位置的币 dp[i-1][j-arr[i]
     * 所以 dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i]]
     * @param coins
     * @return
     */
    private static int[][] commemorativeCoinDp(int[] coins, int aim) {

        if (coins == null || coins.length == 0) {
            return null;
        }
        int[][] dp = new int[coins.length][aim + 1];
        dp[0][0] = 1;
        dp[0][coins[0]] = 1;
        for (int i = 1; i < coins.length; i++) {
            for (int j = 1; j <= aim; j++) {
                int choose = 0;
                if (j >= coins[i]) {
                    choose = dp[i-1][j-coins[i]];
                }
                dp[i][j] = dp[i-1][j] + choose;
            }
        }
        return dp;
    }
}
